#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int size1 = nums1.size(), size2 = nums2.size();
        if (size1 > size2) return findMedianSortedArrays(nums2, nums1);
        int begin = 0, end = size1 - 1;
        int mid1 = (begin + end) / 2;
        int mid2 = (size1 + size2 + 1) / 2 - mid1;
        while (begin < end)
        {
            mid1 = (begin + end) / 2;
            mid2 = (size1 + size2 + 1) / 2 - mid1;
            if (mid1 != size1 && mid2 != 0 && nums1[mid1] < nums2[mid2 - 1])
                begin = mid1 + 1;
            else if (mid1 != 0 && mid2 != size2 && nums1[mid1 + 1] > nums2[mid2])
                end = mid1 - 1;
            else
                break;
        }
        int maxleft = mid1 == 0 ? nums2[size2 - 1] : mid2 == 0 ? nums1[mid2 - 1] : max(nums1[mid1 - 1], nums2[mid2 - 1]);
        if ((size1 + size2) % 2 == 0) return maxleft;
        int minright = mid1 == size1 ? nums2[mid2] : mid2 == size2 ? nums1[mid1] : min(nums1[mid1 - 1], nums2[mid2 - 1]);
        return (maxleft + minright) / 2.0;
    }
};